{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Score After Removals on a Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #tree #depth-first-search #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #树 #深度优先搜索 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从树中删除边的最小分数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>存在一棵无向连通树，树中有编号从 <code>0</code> 到 <code>n - 1</code> 的 <code>n</code> 个节点， 以及 <code>n - 1</code> 条边。</p>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> ，长度为 <code>n</code> ，其中 <code>nums[i]</code> 表示第 <code>i</code> 个节点的值。另给你一个二维整数数组 <code>edges</code> ，长度为 <code>n - 1</code> ，其中 <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> 表示树中存在一条位于节点 <code>a<sub>i</sub></code> 和 <code>b<sub>i</sub></code> 之间的边。</p>\n",
    "\n",
    "<p>删除树中两条 <strong>不同</strong> 的边以形成三个连通组件。对于一种删除边方案，定义如下步骤以计算其分数：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>分别获取三个组件 <strong>每个</strong> 组件中所有节点值的异或值。</li>\n",
    "\t<li><strong>最大</strong> 异或值和 <strong>最小</strong> 异或值的 <strong>差值</strong> 就是这一种删除边方案的分数。</li>\n",
    "</ol>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，三个组件的节点值分别是：<code>[4,5,7]</code>、<code>[1,9]</code> 和 <code>[3,3,3]</code> 。三个异或值分别是 <code>4 ^ 5 ^ 7 = <em><strong>6</strong></em></code>、<code>1 ^ 9 = <em><strong>8</strong></em></code> 和 <code>3 ^ 3 ^ 3 = <em><strong>3</strong></em></code> 。最大异或值是 <code>8</code> ，最小异或值是 <code>3</code> ，分数是 <code>8 - 3 = 5</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回在给定树上执行任意删除边方案可能的 <strong>最小</strong> 分数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/05/03/ex1drawio.png\" style=\"width: 193px; height: 190px;\">\n",
    "<pre><strong>输入：</strong>nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>上图展示了一种删除边方案。\n",
    "- 第 1 个组件的节点是 [1,3,4] ，值是 [5,4,11] 。异或值是 5 ^ 4 ^ 11 = 10 。\n",
    "- 第 2 个组件的节点是 [0] ，值是 [1] 。异或值是 1 = 1 。\n",
    "- 第 3 个组件的节点是 [2] ，值是 [5] 。异或值是 5 = 5 。\n",
    "分数是最大异或值和最小异或值的差值，10 - 1 = 9 。\n",
    "可以证明不存在分数比 9 小的删除边方案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/05/03/ex2drawio.png\" style=\"width: 287px; height: 150px;\">\n",
    "<pre><strong>输入：</strong>nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>上图展示了一种删除边方案。\n",
    "- 第 1 个组件的节点是 [3,4] ，值是 [4,4] 。异或值是 4 ^ 4 = 0 。\n",
    "- 第 2 个组件的节点是 [1,0] ，值是 [5,5] 。异或值是 5 ^ 5 = 0 。\n",
    "- 第 3 个组件的节点是 [2,5] ，值是 [2,2] 。异或值是 2 ^ 2 = 0 。\n",
    "分数是最大异或值和最小异或值的差值，0 - 0 = 0 。\n",
    "无法获得比 0 更小的分数 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>3 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>8</sup></code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "\t<li><code>edges</code> 表示一棵有效的树</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-score-after-removals-on-a-tree](https://leetcode.cn/problems/minimum-score-after-removals-on-a-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-score-after-removals-on-a-tree](https://leetcode.cn/problems/minimum-score-after-removals-on-a-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,5,5,4,11]\\n[[0,1],[1,2],[1,3],[3,4]]', '[5,5,2,4,4,2]\\n[[0,1],[1,2],[5,2],[4,3],[1,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            dct[i].append(j)\n",
    "            dct[j].append(i)\n",
    "        order = 0\n",
    "        start = [-1] * n  # node_to_order\n",
    "        end = [-1] * n\n",
    "        stack = [[0, -1]]\n",
    "        parent = [-1] * n\n",
    "        while stack:\n",
    "            i, fa = stack.pop()\n",
    "            if i >= 0:\n",
    "                start[i] = order\n",
    "                end[i] = order\n",
    "                order += 1\n",
    "                stack.append([~i, fa])\n",
    "                for j in dct[i]:\n",
    "                    if j != fa:  # 注意访问顺序可以进行调整\n",
    "                        stack.append([j, i])\n",
    "                        parent[j] = i\n",
    "            else:\n",
    "                i = ~i\n",
    "                if parent[i] != -1:\n",
    "                    end[parent[i]] = end[i]\n",
    "                for j in dct[i]:\n",
    "                    if j != fa:\n",
    "                        nums[i] ^= nums[j]\n",
    "        total = nums[0]\n",
    "        ans = inf\n",
    "        for i in range(n - 1):\n",
    "            x, y = edges[i]\n",
    "            if parent[x] == y:\n",
    "                x, y = y, x\n",
    "            for j in range(i + 1, n - 1):\n",
    "                a, b = edges[j]\n",
    "                if parent[a] == b:\n",
    "                    a, b = b, a\n",
    "                yy = nums[y]\n",
    "                bb = nums[b]\n",
    "                if start[y] <= start[b] <= end[y]:\n",
    "                    yy ^= bb\n",
    "                if start[b] <= start[y] <= end[b]:\n",
    "                    bb ^= yy\n",
    "                cur = [yy, bb, total ^ yy ^ bb]\n",
    "                cur_ = max(cur) - min(cur)\n",
    "                if cur_ < ans:\n",
    "                    ans = cur_\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        nexts = [set() for _ in range(n)]\n",
    "        bit2i = {\n",
    "            (1<<i):i for i in range(n)\n",
    "        }\n",
    "        for a, b in edges:\n",
    "            nexts[a].add(b)\n",
    "            nexts[b].add(a)\n",
    "        def bfs(x):\n",
    "            visited = 1<<x\n",
    "            q = deque([x])\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                for y in nexts[x]:\n",
    "                    bit = 1<<y\n",
    "                    if visited & bit == 0:\n",
    "                        visited |= bit\n",
    "                        q.append(y)\n",
    "            return visited\n",
    "        @cache\n",
    "        def mask2xor(m):\n",
    "            res = 0\n",
    "            while m:\n",
    "                bit = m & -m\n",
    "                m -= bit\n",
    "                res ^= nums[bit2i[bit]]\n",
    "            return res\n",
    "\n",
    "        allMask = (1<<n) - 1\n",
    "        allXOR = reduce(xor, nums)\n",
    "        edgeSpans = [[] for _ in range(n-1)]\n",
    "        for i, (a, b) in enumerate(edges):\n",
    "            nexts[a].remove(b)\n",
    "            maskA = bfs(a)\n",
    "            nexts[a].add(b)\n",
    "            edgeSpans[i].append(maskA)\n",
    "            edgeSpans[i].append(allMask - maskA)\n",
    "        res = float('inf')\n",
    "        for i, j in combinations(range(n-1), 2):\n",
    "            maskI1, maskI2 = edgeSpans[i]\n",
    "            maskJ1, maskJ2 = edgeSpans[j]\n",
    "            if maskJ1 & maskI1 == maskJ1:\n",
    "                xors = [mask2xor(maskJ1), mask2xor(maskI2)]\n",
    "            elif maskJ1 & maskI2 == maskJ1:\n",
    "                xors = [mask2xor(maskJ1), mask2xor(maskI1)]\n",
    "            elif maskJ2 & maskI1 == maskJ2:\n",
    "                xors = [mask2xor(maskJ2), mask2xor(maskI2)]\n",
    "            else:\n",
    "                xors = [mask2xor(maskJ2), mask2xor(maskI1)]\n",
    "            xors.append(allXOR ^ xors[0] ^ xors[1])\n",
    "            res = min(res, max(xors) - min(xors))\n",
    "        return res\n",
    "            \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        adj = [[] for _ in range(len(nums))]\n",
    "        for e in edges:\n",
    "            adj[e[0]].append(e[1])\n",
    "            adj[e[1]].append(e[0])\n",
    "        begin = [0 for i in range(len(nums))]\n",
    "        end = [0 for i in range(len(nums))]\n",
    "        xor = nums\n",
    "        self.timestamp = 0\n",
    "        self.dfs(0, -1, nums, xor, begin, end, adj)\n",
    "        tree1 = 0 \n",
    "        xor1, xor2, xor3 = 0, 0, 0\n",
    "        n = len(nums)\n",
    "        res = float('inf')\n",
    "        for tree2 in range(1, n - 1):\n",
    "            for tree3 in range(tree2+1, n):\n",
    "                if self.is_ancestor(tree3, tree2, begin, end):\n",
    "                    xor1 = xor[tree1] ^ xor[tree2]\n",
    "                    xor2 = xor[tree2] ^ xor[tree3]\n",
    "                    xor3 = xor[tree3]\n",
    "                elif self.is_ancestor(tree2, tree3, begin, end):\n",
    "                    xor1 = xor[tree1] ^ xor[tree3]\n",
    "                    xor2 = xor[tree2]\n",
    "                    xor3 = xor[tree3] ^ xor[tree2]\n",
    "                else:\n",
    "                    xor1 = xor[tree1] ^ xor[tree2] ^ xor[tree3]\n",
    "                    xor2 = xor[tree2]\n",
    "                    xor3 = xor[tree3]\n",
    "                temp = max([xor1,xor2,xor3]) - min([xor1,xor2,xor3])\n",
    "                res = min(res, temp)\n",
    "        return res\n",
    "\n",
    "    def is_ancestor(self, a, b, begin, end):\n",
    "        return begin[b] < begin[a] and end[b] >= end[a]\n",
    "\n",
    "    def dfs(self, cur, pre, nums, xor, begin, end, adj):\n",
    "        begin[cur] = self.timestamp\n",
    "        self.timestamp += 1\n",
    "        for next in adj[cur]:\n",
    "            if next == pre: continue\n",
    "            self.dfs(next, cur, nums, xor, begin, end, adj)\n",
    "            xor[cur] ^= xor[next]\n",
    "        end[cur] = self.timestamp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        time = [[0] * 2 for _ in range(n)]\n",
    "        p = [0] * n\n",
    "        c = 0\n",
    "\n",
    "        def dfs(node, pre):\n",
    "            nonlocal c\n",
    "            c += 1\n",
    "            time[node][0] = c\n",
    "            res = nums[node]\n",
    "            for ch in g[node]:\n",
    "                if ch != pre:\n",
    "                    dfs(ch, node)\n",
    "                    res ^= p[ch]\n",
    "            time[node][1] = c\n",
    "            p[node] = res\n",
    "\n",
    "        dfs(0, -1)\n",
    "\n",
    "        t = reduce(ixor, nums)\n",
    "        ans = inf\n",
    "        for i, (a, b) in enumerate(edges):\n",
    "            if time[b][0] < time[a][0] <= time[b][1]:\n",
    "                a, b = b, a\n",
    "            for j in range(i + 1, len(edges)):\n",
    "                c, d = edges[j]\n",
    "                if time[d][0] < time[c][0] <= time[d][1]:\n",
    "                    c, d = d, c\n",
    "                \n",
    "                if time[b][0] < time[d][0] <= time[b][1]:\n",
    "                    x, y, z = p[d], p[b] ^ p[d], t ^ p[b]\n",
    "                elif time[d][0] < time[b][0] <= time[d][1]:\n",
    "                    x, y, z = p[b], p[d] ^ p[b], t ^ p[d]\n",
    "                else:\n",
    "                    x, y, z = p[b], p[d], t ^ p[b] ^ p[d]\n",
    "\n",
    "                ans = min(ans, max(x, y, z) - min(x, y, z))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        tol = 0\n",
    "        for num in nums:\n",
    "            tol ^= num \n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        XOR = [0] * n \n",
    "        def get_XOR(node, par):\n",
    "            XOR[node] = nums[node]\n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                get_XOR(nei, node)\n",
    "                XOR[node] ^= XOR[nei]\n",
    "        res = float('inf')\n",
    "        def dfs(node, par, subsum):\n",
    "            nonlocal res \n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue\n",
    "                p1 = XOR[nei]\n",
    "                p2 = subsum ^ p1 \n",
    "                p3 = tol ^ subsum\n",
    "                res = min(res, max(p1, p2, p3) - min(p1, p2, p3))\n",
    "                dfs(nei, node, subsum)\n",
    "        for i in range(n):\n",
    "            get_XOR(i, - 1)\n",
    "            for node in graph[i]:\n",
    "                dfs(node, i, XOR[node])\n",
    "        return res \n",
    "                \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        xor, in_, out, clock = [0] * n, [0] * n, [0] * n, 0\n",
    "        def dfs(u, fa):\n",
    "            nonlocal clock\n",
    "            clock += 1\n",
    "            in_[u] = clock\n",
    "            xor[u] = nums[u]\n",
    "            for v in g[u]:\n",
    "                if v != fa:\n",
    "                    dfs(v, u)\n",
    "                    xor[u] ^= xor[v]\n",
    "            out[u] = clock\n",
    "        dfs(0, -1)\n",
    "\n",
    "        res = inf\n",
    "        for i in range(2, n):\n",
    "            for j in range(1, i):\n",
    "                if in_[i] < in_[j] <= out[i]:\n",
    "                    x, y, z = xor[j], xor[i] ^ xor[j], xor[0] ^ xor[i]\n",
    "                elif in_[j] < in_[i] <= out[j]:\n",
    "                    x, y, z = xor[i], xor[i] ^ xor[j], xor[0] ^ xor[j]\n",
    "                else:\n",
    "                    x, y, z = xor[i], xor[j], xor[0] ^ xor[i] ^ xor[j]\n",
    "                res = min(res, max(x, y, z) - min(x, y, z))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        clock, xor, _in, out = 0, [0] * n,[0] * n,[0] * n\n",
    "        def dfs(i, fa):\n",
    "            nonlocal clock\n",
    "            clock += 1\n",
    "            _in[i] = clock\n",
    "            xor[i] = nums[i]\n",
    "            for j in g[i]:\n",
    "                if j != fa:\n",
    "                    dfs(j, i)\n",
    "                    xor[i] ^= xor[j]\n",
    "            out[i] = clock\n",
    "        dfs(0, -1)\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(2, n):\n",
    "            for j in range(1, i):\n",
    "                if _in[i] < _in[j] <= out[i]:\n",
    "                    x, y, z = xor[j], xor[i] ^ xor[j], xor[i] ^ xor[0]\n",
    "                elif _in[j] < _in[i] <= out[j]:\n",
    "                    x, y, z = xor[i], xor[i] ^ xor[j], xor[j] ^ xor[0]\n",
    "                else:\n",
    "                    x, y, z = xor[i], xor[j], xor[j] ^ xor[0] ^ xor[i]\n",
    "                ans = min(ans, max(x, y, z) - min(x, y, z))\n",
    "                if ans == 0:\n",
    "                    break\n",
    "        return ans\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        g = [[] for _ in range(n)]\r\n",
    "        for x, y in edges:\r\n",
    "            g[x].append(y)\r\n",
    "            g[y].append(x)\r\n",
    "\r\n",
    "        xor, in_, out, clock = [0] * n, [0] * n, [0] * n, 0\r\n",
    "        def dfs(x: int, fa: int) -> None:\r\n",
    "            nonlocal clock\r\n",
    "            clock += 1\r\n",
    "            in_[x] = clock\r\n",
    "            xor[x] = nums[x]\r\n",
    "            for y in g[x]:\r\n",
    "                if y != fa:\r\n",
    "                    dfs(y, x)\r\n",
    "                    xor[x] ^= xor[y]\r\n",
    "            out[x] = clock\r\n",
    "        dfs(0, -1)\r\n",
    "\r\n",
    "        ans = inf\r\n",
    "        for i in range(2, n):\r\n",
    "            for j in range(1, i):\r\n",
    "                if in_[i] < in_[j] <= out[i]:  # i 是 j 的祖先节点\r\n",
    "                    x, y, z = xor[j], xor[i] ^ xor[j], xor[0] ^ xor[i]\r\n",
    "                elif in_[j] < in_[i] <= out[j]:  # j 是 i 的祖先节点\r\n",
    "                    x, y, z = xor[i], xor[i] ^ xor[j], xor[0] ^ xor[j]\r\n",
    "                else:  # 删除的两条边分别属于两颗不相交的子树\r\n",
    "                    x, y, z = xor[i], xor[j], xor[0] ^ xor[i] ^ xor[j]\r\n",
    "                ans = min(ans, max(x, y, z) - min(x, y, z))\r\n",
    "                # 注：把 min max 拆开，改为下面的注释，可以明显加快速度\r\n",
    "                # mn = mx = x\r\n",
    "                # if y < mn: mn = y \r\n",
    "                # elif y > mx: mx = y\r\n",
    "                # if z < mn: mn = z \r\n",
    "                # elif z > mx: mx = z\r\n",
    "                # if mx - mn < ans: ans = mx - mn\r\n",
    "                if ans == 0: return 0  # 提前退出\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        xor, in_, out, clock = [0] * n, [0] * n, [0] * n, 0\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "            nonlocal clock\n",
    "            clock += 1\n",
    "            in_[x] = clock\n",
    "            xor[x] = nums[x]\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "                    xor[x] ^= xor[y]\n",
    "            out[x] = clock\n",
    "        dfs(0, -1)\n",
    "\n",
    "        ans = inf\n",
    "        for i in range(2, n):\n",
    "            for j in range(1, i):\n",
    "                if in_[i] < in_[j] <= out[i]:  # i 是 j 的祖先节点\n",
    "                    x, y, z = xor[j], xor[i] ^ xor[j], xor[0] ^ xor[i]\n",
    "                elif in_[j] < in_[i] <= out[j]:  # j 是 i 的祖先节点\n",
    "                    x, y, z = xor[i], xor[i] ^ xor[j], xor[0] ^ xor[j]\n",
    "                else:  # 删除的两条边分别属于两颗不相交的子树\n",
    "                    x, y, z = xor[i], xor[j], xor[0] ^ xor[i] ^ xor[j]\n",
    "                ans = min(ans, max(x, y, z) - min(x, y, z))\n",
    "                # 注：把 min max 拆开，改为下面的注释，可以明显加快速度\n",
    "                # mn = mx = x\n",
    "                # if y < mn: mn = y \n",
    "                # elif y > mx: mx = y\n",
    "                # if z < mn: mn = z \n",
    "                # elif z > mx: mx = z\n",
    "                # if mx - mn < ans: ans = mx - mn\n",
    "                if ans == 0: return 0  # 提前退出\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        \n",
    "        g = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        tot = reduce(xor, nums)\n",
    "        \n",
    "        def dfs(root, fa):\n",
    "            nonlocal d\n",
    "            cur = nums[root]\n",
    "            for nei in g[root]:\n",
    "                if nei != fa:\n",
    "                    cur ^= dfs(nei, root)\n",
    "            d[root] = cur\n",
    "            return cur\n",
    "    \n",
    "        ans = float('inf')\n",
    "        n = len(nums)\n",
    "\n",
    "        def dfs2(root, fa, val, valb):\n",
    "            nonlocal ans\n",
    "            for nei in g[root]:\n",
    "                if nei != fa:\n",
    "                    ans = min(ans, max(val, valb ^ d[nei], d[nei]) - min(val, valb ^ d[nei], d[nei]))\n",
    "                    dfs2(nei, root, val, valb)\n",
    "\n",
    "        for i in range(n):\n",
    "            d = {}\n",
    "            dfs(i, -1)\n",
    "            for nei in g[i]:\n",
    "                dfs2(nei, i, tot ^ d[nei], d[nei])\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        \n",
    "        g = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        tot = reduce(xor, nums)\n",
    "        \n",
    "        def dfs(root, fa):\n",
    "            nonlocal d\n",
    "            cur = nums[root]\n",
    "            for nei in g[root]:\n",
    "                if nei != fa:\n",
    "                    cur ^= dfs(nei, root)\n",
    "            d[root] = cur\n",
    "            return cur\n",
    "    \n",
    "        ans = float('inf')\n",
    "        n = len(nums)\n",
    "\n",
    "        def dfs2(root, fa, val, valb):\n",
    "            nonlocal ans\n",
    "            for nei in g[root]:\n",
    "                if nei != fa:\n",
    "                    ans = min(ans, max(val, valb ^ d[nei], d[nei]) - min(val, valb ^ d[nei], d[nei]))\n",
    "                    dfs2(nei, root, val, valb)\n",
    "        \n",
    "        for i in range(n):\n",
    "            d = {}\n",
    "            dfs(i, -1)\n",
    "            for nei in g[i]:\n",
    "                dfs2(nei, i, tot ^ d[nei], d[nei])\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        tol = 0\n",
    "        for num in nums:\n",
    "            tol ^= num \n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        XOR = [0] * n \n",
    "        def get_XOR(node, par):\n",
    "            XOR[node] = nums[node]\n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                get_XOR(nei, node)\n",
    "                XOR[node] ^= XOR[nei]\n",
    "        res = float('inf')\n",
    "        def dfs(node, par, subsum):\n",
    "            nonlocal res \n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue\n",
    "                p1 = XOR[nei]\n",
    "                p2 = subsum ^ p1 \n",
    "                p3 = tol ^ subsum\n",
    "                res = min(res, max(p1, p2, p3) - min(p1, p2, p3))\n",
    "                dfs(nei, node, subsum)\n",
    "        for i in range(n):\n",
    "            get_XOR(i, - 1)\n",
    "            for node in graph[i]:\n",
    "                dfs(node, i, XOR[node])\n",
    "        return res \n",
    "                \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DFS:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def gen_dfs_order_recursion(dct):\n",
    "        # 模板：生成深搜序即 dfs 序以及对应子树编号区间\n",
    "        def dfs(x):\n",
    "            nonlocal order\n",
    "            start[x] = order\n",
    "            order += 1\n",
    "            for y in dct[x]:\n",
    "                if start[y] == -1:\n",
    "                    dfs(y)\n",
    "            end[x] = order - 1\n",
    "            return\n",
    "\n",
    "        n = len(dct)\n",
    "        order = 0\n",
    "        start = [-1] * n\n",
    "        end = [-1]*n\n",
    "        dfs(0)\n",
    "        return start, end\n",
    "\n",
    "    @staticmethod\n",
    "    def gen_bfs_order_iteration(dct):\n",
    "        # 模板：生成深搜序即 dfs 序以及对应子树编号区间\n",
    "        n = len(dct)\n",
    "        for i in range(n):\n",
    "            dct[i].sort(reverse=True)  # 按照子节点编号从小到大进行遍历\n",
    "        order = 0\n",
    "        start = [-1] * n  # node_to_order\n",
    "        end = [-1]*n\n",
    "        parent = [-1]*n\n",
    "        stack = [[0, -1, 0]]\n",
    "        depth = [0]*n\n",
    "        order_to_node = [-1]*n\n",
    "        while stack:\n",
    "            i, fa, d = stack.pop()\n",
    "            if i >= 0:\n",
    "                start[i] = order\n",
    "                order_to_node[order] = i\n",
    "                end[i] = order\n",
    "                depth[i] = d\n",
    "                order += 1\n",
    "                stack.append([~i, fa, d])\n",
    "                for j in dct[i]:\n",
    "                    if j != fa:  # 注意访问顺序可以进行调整\n",
    "                        parent[j] = i\n",
    "                        stack.append([j, i, d+1])\n",
    "            else:\n",
    "                i = ~i\n",
    "                if parent[i] != -1:\n",
    "                    end[parent[i]] = end[i]\n",
    "\n",
    "        return start, end\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            dct[i].append(j)\n",
    "            dct[j].append(i)\n",
    "            \n",
    "        parent= [-1]*n\n",
    "        start, end = DFS().gen_bfs_order_iteration(dct)\n",
    "        \n",
    "        def dfs(x, fa):\n",
    "            res = nums[x]\n",
    "            for y in dct[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "                    parent[y] = x\n",
    "                    res ^= sub[y]\n",
    "            sub[x] = res\n",
    "            return \n",
    "        \n",
    "        total = reduce(xor, nums)\n",
    "        \n",
    "        sub = [0]*n\n",
    "        \n",
    "        dfs(0, -1)\n",
    "        ans = inf\n",
    "        for i in range(n-1):\n",
    "            x, y = edges[i]\n",
    "            if parent[x] == y:\n",
    "                x, y = y, x\n",
    "            for j in range(i+1, n-1):\n",
    "                a, b = edges[j]\n",
    "                if parent[a] == b:\n",
    "                    a, b = b, a\n",
    "      \n",
    "                yy = sub[y]\n",
    "                bb = sub[b]\n",
    "                if start[y] <= start[b] <= end[y]:\n",
    "                    yy ^= bb\n",
    "                if start[b] <= start[y] <= end[b]:\n",
    "                    bb ^= yy\n",
    "                cur = [yy, bb, total^yy^bb]\n",
    "                cur_ = max(cur) - min(cur)\n",
    "                if cur_ < ans:\n",
    "                    ans =cur_\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "            \n",
    "        tin = [0] * n\n",
    "        tout = [0] * n\n",
    "        xor = [0] * n\n",
    "        t = 0\n",
    "        def dfs(x: int, p: int):\n",
    "            nonlocal t\n",
    "            t += 1\n",
    "            tin[x] = t\n",
    "            xor[x] = nums[x]\n",
    "            for y in g[x]:\n",
    "                if y == p: continue\n",
    "                dfs(y, x)\n",
    "                xor[x] ^= xor[y]\n",
    "            t += 1\n",
    "            tout[x] = t\n",
    "        \n",
    "        dfs(0, -1)\n",
    "\n",
    "        ans = inf\n",
    "        for i in range(2, n):\n",
    "            for j in range(1, i):\n",
    "                if tin[i] < tin[j] <= tout[i]:  # i 是 j 的祖先节点\n",
    "                    x, y, z = xor[j], xor[i] ^ xor[j], xor[0] ^ xor[i]\n",
    "                elif tin[j] < tin[i] <= tout[j]:  # j 是 i 的祖先节点\n",
    "                    x, y, z = xor[i], xor[i] ^ xor[j], xor[0] ^ xor[j]\n",
    "                else:  # 删除的两条边分别属于两颗不相交的子树\n",
    "                    x, y, z = xor[i], xor[j], xor[0] ^ xor[i] ^ xor[j]\n",
    "                ans = min(ans, max(x, y, z) - min(x, y, z))\n",
    "            if ans == 0: return 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        \n",
    "        g = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        tot = reduce(xor, nums)\n",
    "        \n",
    "        def dfs(root, fa):\n",
    "            nonlocal d\n",
    "            cur = nums[root]\n",
    "            for nei in g[root]:\n",
    "                if nei != fa:\n",
    "                    cur ^= dfs(nei, root)\n",
    "            d[root] = cur\n",
    "            return cur\n",
    "    \n",
    "        ans = float('inf')\n",
    "        n = len(nums)\n",
    "\n",
    "        def dfs2(root, fa, val, valb):\n",
    "            nonlocal ans\n",
    "            for nei in g[root]:\n",
    "                if nei != fa:\n",
    "                    ans = min(ans, max(val, valb ^ d[nei], d[nei]) - min(val, valb ^ d[nei], d[nei]))\n",
    "                    dfs2(nei, root, val, valb)\n",
    "        \n",
    "        for i in range(n):\n",
    "            d = {}\n",
    "            dfs(i, -1)\n",
    "            for nei in g[i]:\n",
    "                dfs2(nei, i, tot ^ d[nei], d[nei])\n",
    "                if ans == 0:\n",
    "                    return ans\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from math import inf\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        xor, in_, out, clock = [0] * n, [0] * n, [0] * n, 0\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "            nonlocal clock\n",
    "            clock += 1\n",
    "            in_[x] = clock\n",
    "            xor[x] = nums[x]\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "                    xor[x] ^= xor[y]\n",
    "            out[x] = clock\n",
    "        dfs(0, -1)\n",
    "\n",
    "        ans = inf\n",
    "        for i in range(2, n):\n",
    "            for j in range(1, i):\n",
    "                if in_[i] < in_[j] <= out[i]:  # i 是 j 的祖先节点\n",
    "                    x, y, z = xor[j], xor[i] ^ xor[j], xor[0] ^ xor[i]\n",
    "                elif in_[j] < in_[i] <= out[j]:  # j 是 i 的祖先节点\n",
    "                    x, y, z = xor[i], xor[i] ^ xor[j], xor[0] ^ xor[j]\n",
    "                else:  # 删除的两条边分别属于两颗不相交的子树\n",
    "                    x, y, z = xor[i], xor[j], xor[0] ^ xor[i] ^ xor[j]\n",
    "                ans = min(ans, max(x, y, z) - min(x, y, z))\n",
    "                if ans == 0: \n",
    "                    return 0  # 提前退出\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        G = defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            G[a].append(b)\n",
    "            G[b].append(a)\n",
    "        \n",
    "        def dfsxor(cur,par):\n",
    "            if len(G[cur]) == 1 and par != -1:\n",
    "                D[cur] = nums[cur]\n",
    "                return nums[cur]\n",
    "            res = nums[cur]\n",
    "            for nxt in G[cur]:\n",
    "                if nxt == par:continue\n",
    "                res ^= dfsxor(nxt,cur)\n",
    "            D[cur] = res\n",
    "            return res\n",
    "        res,s = inf,0\n",
    "        for i in nums:s ^= i\n",
    "\n",
    "        def dfs(cur,par,a):\n",
    "            nonlocal res\n",
    "            if len(G[cur]) == 1 and par != -1:return\n",
    "            for nxt in G[cur]:\n",
    "                if nxt == par:continue\n",
    "                b = D[nxt]\n",
    "                res = min(res,max([a^b,b,s^a])-min([a^b,b,s^a]))\n",
    "                dfs(nxt,cur,a)\n",
    "            return\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            D = {}\n",
    "            dfsxor(i,-1)\n",
    "            for p1 in G[i]:\n",
    "                a = D[p1]\n",
    "                dfs(p1,i,a)\n",
    "        return res\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        xor, in_, out, clock = [0] * n, [0] * n, [0] * n, 0\n",
    "        def dfs(x: int, fa: int) -> None:\n",
    "            nonlocal clock\n",
    "            clock += 1\n",
    "            in_[x] = clock\n",
    "            xor[x] = nums[x]\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs(y, x)\n",
    "                    xor[x] ^= xor[y]\n",
    "            out[x] = clock\n",
    "        dfs(0, -1)\n",
    "\n",
    "        ans = inf\n",
    "        for i in range(2, n):\n",
    "            for j in range(1, i):\n",
    "                if in_[i] < in_[j] <= out[i]:  # i 是 j 的祖先节点\n",
    "                    x, y, z = xor[j], xor[i] ^ xor[j], xor[0] ^ xor[i]\n",
    "                elif in_[j] < in_[i] <= out[j]:  # j 是 i 的祖先节点\n",
    "                    x, y, z = xor[i], xor[i] ^ xor[j], xor[0] ^ xor[j]\n",
    "                else:  # 删除的两条边分别属于两颗不相交的子树\n",
    "                    x, y, z = xor[i], xor[j], xor[0] ^ xor[i] ^ xor[j]\n",
    "                ans = min(ans, max(x, y, z) - min(x, y, z))\n",
    "                # 注：把 min max 拆开，改为下面的注释，可以明显加快速度\n",
    "                # mn = mx = x\n",
    "                # if y < mn: mn = y \n",
    "                # elif y > mx: mx = y\n",
    "                # if z < mn: mn = z \n",
    "                # elif z > mx: mx = z\n",
    "                # if mx - mn < ans: ans = mx - mn\n",
    "                if ans == 0: return 0  # 提前退出\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums) \n",
    "\n",
    "        xor = [0] * n \n",
    "        in_ = [0] * n \n",
    "        out_ = [0] * n\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        for [a,b] in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        clock = 0\n",
    "        def dfs(u, pre):\n",
    "            nonlocal clock \n",
    "            clock += 1\n",
    "            in_[u] = clock \n",
    "            xor[u] = nums[u] \n",
    "\n",
    "            for v in g[u]:\n",
    "                if v != pre:\n",
    "                    xor[u] ^= dfs(v, u)\n",
    "            \n",
    "            out_[u] = clock \n",
    "\n",
    "            return xor[u] \n",
    "        \n",
    "        dfs(0, 0)\n",
    "\n",
    "        m = len(edges)\n",
    "        ans = float('inf')\n",
    "        for i in range(m-1):\n",
    "            for j in range(i+1, m):\n",
    "                [a1,b1] = edges[i]\n",
    "                [a2,b2] = edges[j]\n",
    "                if in_[a1] > in_[b1]:\n",
    "                    a1,b1 = b1,a1 \n",
    "                if in_[a2] > in_[b2]:\n",
    "                    a2,b2 = b2,a2 \n",
    "                x,y,z = 0,0,0\n",
    "                if in_[b1] < in_[b2] <= out_[b1]:\n",
    "                    x, y, z = xor[0] ^ xor[b1], xor[b1] ^ xor[b2], xor[b2]\n",
    "                elif in_[b2] < in_[b1] <= out_[b2]:\n",
    "                    x, y, z = xor[0] ^ xor[b2], xor[b2] ^ xor[b1], xor[b1]\n",
    "                else:\n",
    "                    x, y, z = xor[0] ^ xor[b1] ^ xor[b2], xor[b1], xor[b2]\n",
    "                mx_,mi_ = max(x,y,z), min(x,y,z)\n",
    "                \n",
    "                if ans > mx_-mi_:\n",
    "                    ans = mx_-mi_\n",
    " \n",
    "        \n",
    "        return ans \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n=len(nums)\n",
    "        arr=[[] for _ in range(n)]\n",
    "        clock=0\n",
    "        xor=[0 for _ in range(n)]\n",
    "        in_clock=[0 for _ in range(n)]\n",
    "        out_clock=[0 for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            arr[edge[0]].append(edge[1])\n",
    "            arr[edge[1]].append(edge[0])\n",
    "        def dfs(x, fa):\n",
    "            nonlocal clock\n",
    "            clock+=1\n",
    "            in_clock[x]=clock\n",
    "            xor[x]=nums[x]\n",
    "            for y in arr[x]:\n",
    "                if y!=fa:\n",
    "                    dfs(y,x)\n",
    "                    xor[x]^=xor[y]\n",
    "            out_clock[x]=clock\n",
    "        dfs(0,-1)\n",
    "        ans=float('inf')\n",
    "        # 不选根节点\n",
    "        for i in range(2,n):\n",
    "            for j in range(1,i):\n",
    "                # i是j的祖先\n",
    "                if in_clock[i]<in_clock[j] and in_clock[j]<=out_clock[i]:\n",
    "                    a,b,c=xor[j],xor[i]^xor[j],xor[0]^xor[i]\n",
    "                # j是i的祖先\n",
    "                elif in_clock[j]<in_clock[i] and in_clock[i]<=out_clock[j]:\n",
    "                    a,b,c=xor[i],xor[j]^xor[i],xor[0]^xor[j]\n",
    "                else:\n",
    "                    a,b,c=xor[i],xor[j],xor[0]^xor[i]^xor[j]\n",
    "                ans=min(ans, max(a,b,c)-min(a,b,c))\n",
    "                if ans==0:\n",
    "                    return 0\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        G = defaultdict(list)\n",
    "        S = set()\n",
    "        for a,b in edges:\n",
    "            G[a].append(b)\n",
    "            G[b].append(a)\n",
    "        \n",
    "        def dfsxor(cur,par):\n",
    "            if len(G[cur]) == 1 and par != -1:\n",
    "                D[cur] = nums[cur]\n",
    "                return nums[cur]\n",
    "            res = nums[cur]\n",
    "            for nxt in G[cur]:\n",
    "                if nxt == par:continue\n",
    "                res ^= dfsxor(nxt,cur)\n",
    "            D[cur] = res\n",
    "            return res\n",
    "        res,s = inf,0\n",
    "        for i in nums:s ^= i\n",
    "        def dfs(cur,par):\n",
    "            nonlocal res\n",
    "            if len(G[cur]) == 1:return\n",
    "            for nxt in G[cur]:\n",
    "                if nxt == par or nxt == p1:continue\n",
    "                b = D[nxt]\n",
    "                c = s ^ a ^ b\n",
    "                res = min(res,max([a,b,c])-min([a,b,c]))\n",
    "                dfs(nxt,cur)\n",
    "            return\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if len(G[i]) < 2:continue\n",
    "            D = {}\n",
    "            dfsxor(i,-1)\n",
    "            for p1 in G[i]:\n",
    "                a = D[p1]\n",
    "                dfs(i,-1)\n",
    "        return res\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        G = defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            G[a].append(b)\n",
    "            G[b].append(a)\n",
    "        \n",
    "        def dfsxor(cur,par):\n",
    "            if len(G[cur]) == 1 and par != -1:\n",
    "                D[cur] = nums[cur]\n",
    "                return nums[cur]\n",
    "            res = nums[cur]\n",
    "            for nxt in G[cur]:\n",
    "                if nxt == par:continue\n",
    "                res ^= dfsxor(nxt,cur)\n",
    "            D[cur] = res\n",
    "            return res\n",
    "        res,s = inf,0\n",
    "        for i in nums:s ^= i\n",
    "        def dfs(cur,par):\n",
    "            nonlocal res\n",
    "            if len(G[cur]) == 1:\n",
    "                b = D[cur]\n",
    "                c = s ^ a ^ b\n",
    "                res = min(res,max([a,b,c])-min([a,b,c]))\n",
    "                return\n",
    "            for nxt in G[cur]:\n",
    "                if nxt == par or nxt == p1:continue\n",
    "                b = D[nxt]\n",
    "                c = s ^ a ^ b\n",
    "                res = min(res,max([a,b,c])-min([a,b,c]))\n",
    "                dfs(nxt,cur)\n",
    "            return\n",
    "        for i in range(len(nums)):\n",
    "            if len(G[i]) < 2:continue\n",
    "            D = {}\n",
    "            dfsxor(i,-1)\n",
    "            for p1 in G[i]:\n",
    "                a = D[p1]\n",
    "                dfs(i,-1)\n",
    "        return res\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        inTime, outTime = [0] * n, [0] * n\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        t = 0\n",
    "        res = [0] * n\n",
    "\n",
    "        def dfs(node, fa):\n",
    "            nonlocal t\n",
    "            res[node] = nums[node]\n",
    "            inTime[node] = t\n",
    "            for nxt in g[node]:\n",
    "                if nxt != fa:\n",
    "                    t += 1\n",
    "                    dfs(nxt, node)\n",
    "                    res[node] ^= res[nxt]\n",
    "            t += 1\n",
    "            outTime[node] = t\n",
    "            return res[node]\n",
    "\n",
    "        dfs(0, -1)\n",
    "        total = reduce(xor, nums)\n",
    "        ans = inf\n",
    "\n",
    "        def faAndChild(x):\n",
    "            a, b = x\n",
    "            if inTime[a] < inTime[b]:\n",
    "                return x\n",
    "            return [b, a]\n",
    "\n",
    "        for i in range(n - 2):\n",
    "            for j in range(i + 1, n - 1):\n",
    "                head1, head2 = faAndChild(edges[i])[1], faAndChild(edges[j])[1]\n",
    "                if inTime[head1] >= inTime[head2] and outTime[head1] <= outTime[head2]:\n",
    "                    tmp2 = res[head2] ^ res[head1]\n",
    "                    tmp1 = res[head1]\n",
    "                    ans = min(ans, max(tmp1, tmp2, total ^ res[head2]) - min(tmp1, tmp2, total ^ res[head2]))\n",
    "                elif inTime[head1] <= inTime[head2] and outTime[head1] >= outTime[head2]:\n",
    "                    tmp1 = res[head1] ^ res[head2]\n",
    "                    tmp2 = res[head2]\n",
    "                    ans = min(ans, max(tmp1, tmp2, total ^ res[head1]) - min(tmp1, tmp2, total ^ res[head1]))\n",
    "                else:\n",
    "                    tmp1 = res[head1]\n",
    "                    tmp2 = res[head2]\n",
    "                    ans = min(ans, max(tmp1, tmp2, total ^ tmp1 ^ tmp2) - min(tmp1, tmp2, total ^ tmp1 ^ tmp2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, f: List[int], edges: List[List[int]]) -> int:\n",
    "        n, res, vs = len(f), 123456789, []\n",
    "        g, t = [set() for _ in range(n)], [[0, 0] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].add(v); g[v].add(u)\n",
    "\n",
    "        def dfs(u):\n",
    "            t[u][0] = len(vs)\n",
    "            for v in g[u]:\n",
    "                g[v].remove(u)\n",
    "                vs.append(v)\n",
    "                dfs(v)\n",
    "                f[u] ^= f[v]\n",
    "            t[u][1] = len(vs)\n",
    "\n",
    "        dfs(1)\n",
    "\n",
    "        for v1, v2 in combinations(vs, 2):\n",
    "            x = [f[1] ^ f[v1], f[v1], f[v2]]\n",
    "            x[t[v1][0] < t[v2][0] <= t[v1][1]] ^= x[2]\n",
    "            x.sort()\n",
    "            if (tr := x[2] - x[0]) == 0: return 0\n",
    "            elif res > tr: res = tr\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "    l = len(nums)\n",
    "    c = [[] for _ in range(l)]\n",
    "    for a, b in edges:\n",
    "      c[a].append(b)\n",
    "      c[b].append(a)\n",
    "\n",
    "    def dfs(aRt, aMk, aR):\n",
    "      if 0 == aMk[aRt]:\n",
    "        m[aRt] = 1\n",
    "        av = nums[aRt]\n",
    "        ch = []\n",
    "        for n in c[aRt]:\n",
    "          if 0 == aMk[n]:\n",
    "            ch.append(n)\n",
    "            cv, cc = dfs(n, aMk, aR)\n",
    "            ch += cc\n",
    "            av = av ^ cv\n",
    "        # print(f\"assign {aRt} {av} {ch}\")\n",
    "        aR[aRt] = (av, ch)\n",
    "        return av, ch\n",
    "      else:\n",
    "        return 0, []\n",
    "    m = [0] * l\n",
    "    r = {}\n",
    "    av, ch = dfs(0, m, r)\n",
    "    # print(f\"av {av} c {ch}, r {r}\")\n",
    "    ret = -1\n",
    "    for c1 in range(1, l):\n",
    "      for c2 in range(c1 + 1, l):\n",
    "        if c1 in r[c2][1]:\n",
    "          v1 = r[c1][0]\n",
    "          v2 = av ^ r[c2][0]\n",
    "          v3 = r[c2][0] ^ v1\n",
    "          # print(\"p1\")\n",
    "        else:\n",
    "          v1 = r[c2][0]\n",
    "          if c2 in r[c1][1]:\n",
    "            # print(\"p2\")\n",
    "            v2 = av ^ r[c1][0]\n",
    "            v3 = r[c1][0] ^ v1\n",
    "          else:\n",
    "            # print(\"p3\")\n",
    "            v2 = r[c1][0]\n",
    "            v3 = av ^ v2 ^ v1\n",
    "        a = max(v1, v2, v3)\n",
    "        b = min(v1, v2, v3)\n",
    "        # print(f\"c {c1} {c2} {a} {b}\")\n",
    "        d = a - b\n",
    "        if -1 == ret or d < ret:\n",
    "          # print(f\"d {d} cut {c1} {c2} v({v1},  {v2},  {v3})\")\n",
    "          ret = d\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 首先我们根据节点关系建树,假设0为根节点,并通过dp求出以每个节点为根的子树的异或和;由于异或和的特殊性质,假设我们删除(u->v)这条边,那么对于u的根节点r其现在的节点异或和为dp[r] ^ dp[v];所以我们可以先枚举第一次删除的边,求出现在两个连通块的异或和,再枚举第二次删除的边,同时判断其属于第一个连通块还是第二个连通块,同时我们还需要判断第二次删除的边与第一次删除的边是否存在父子关系,并分情况计算其差值即可。时间复杂度:O(n ** 2)\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        G = collections.defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            G[u].append(v)\n",
    "            G[v].append(u)\n",
    "            \n",
    "        # 假设0为根节点\n",
    "        dep = [-1 for _ in range(n)]\n",
    "        dep[0] = 0\n",
    "        queue = collections.deque()\n",
    "        queue.append(0)\n",
    "        par = {}\n",
    "        par[0] = -1\n",
    "        child = collections.defaultdict(list)\n",
    "        deg = [0 for _ in range(n)]\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nxt in G[cur]:\n",
    "                if dep[nxt] == -1:\n",
    "                    dep[nxt] = dep[cur] + 1\n",
    "                    par[nxt] = cur\n",
    "                    child[cur].append(nxt)\n",
    "                    queue.append(nxt)\n",
    "                    deg[cur] += 1\n",
    "                    \n",
    "        # dp[i]表示以i为子树的异或和\n",
    "        dp = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if deg[i] == 0:\n",
    "                queue.append(i)\n",
    "                dp[i] = nums[i]\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            pa = par[cur]\n",
    "            if pa == -1:\n",
    "                continue\n",
    "            deg[pa] -= 1\n",
    "            if deg[pa] == 0:\n",
    "                t = nums[pa]\n",
    "                for chi in child[pa]:\n",
    "                    t ^= dp[chi]\n",
    "                dp[pa] = t\n",
    "                queue.append(pa)\n",
    "                \n",
    "        keda = collections.defaultdict(set)\n",
    "        def bfs(x,dep,G):\n",
    "            nonlocal keda\n",
    "            queue = collections.deque()\n",
    "            queue.append(x)\n",
    "            keda[x].add(x)\n",
    "            while queue:\n",
    "                cur = queue.popleft()\n",
    "                for nxt in G[cur]:\n",
    "                    if dep[nxt] > dep[cur] and nxt not in keda[x]:\n",
    "                        keda[x].add(nxt)\n",
    "                        queue.append(nxt)\n",
    "            return\n",
    "        \n",
    "        for i in range(n):\n",
    "            bfs(i,dep,G)\n",
    "            \n",
    "        ans = float('inf')\n",
    "        for i in range(n - 1):\n",
    "            u1,v1 = edges[i][0],edges[i][1]\n",
    "            if dep[u1] > dep[v1]:\n",
    "                u1,v1 = v1,u1\n",
    "            t1 = dp[0] ^ dp[v1]\n",
    "            t2 = dp[v1]\n",
    "            # 根节点分别为0,v1\n",
    "            for j in range(n - 1):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                u2,v2 = edges[j][0],edges[j][1]\n",
    "                if dep[u2] > dep[v2]:\n",
    "                    u2,v2 = v2,u2\n",
    "                # 判断u2,v2属于哪个连通块\n",
    "                if u2 in keda[v1]:\n",
    "                    # 属于第二个\n",
    "                    t3 = t2 ^ dp[v2]\n",
    "                    t4 = dp[v2]\n",
    "                    ans = min(ans,max(t1,t3,t4) - min(t1,t3,t4))\n",
    "                else:\n",
    "                    # 属于第一个\n",
    "                    if v1 not in keda[v2]:\n",
    "                        t3 = t1 ^ dp[v2]\n",
    "                        t4 = dp[v2]\n",
    "                    else:\n",
    "                        tmp = dp[v2] ^ dp[v1]\n",
    "                        t3 = t1 ^ tmp\n",
    "                        t4 = tmp\n",
    "                    ans = min(ans,max(t2,t3,t4) - min(t2,t3,t4))\n",
    "                        \n",
    "        return ans     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        depth, vals = [0] * n, [0] * n\n",
    "        adj_list = [list() for i in range(n)]\n",
    "        for u, v in edges:\n",
    "            adj_list[u].append(v)\n",
    "            adj_list[v].append(u)\n",
    "        vis = [0] * n\n",
    "        same_tree = [[False] * n for i in range(n)]\n",
    "        \n",
    "        def dfs(u, d, path):\n",
    "            depth[u] = d\n",
    "            val = nums[u]\n",
    "            for p in path:\n",
    "                same_tree[p][u] = same_tree[u][p] = True\n",
    "            path.append(u)\n",
    "            vis[u] = -1\n",
    "            for v in adj_list[u]:\n",
    "                if vis[v] == 0:\n",
    "                    val ^= dfs(v, d + 1, path)\n",
    "            vis[u] = 1\n",
    "            path.pop()\n",
    "            vals[u] = val\n",
    "            return val\n",
    "        \n",
    "        dfs(0, 0, [])\n",
    "        m = len(edges)\n",
    "        \n",
    "        def get_edge(idx):\n",
    "            u, v = edges[idx]\n",
    "            if depth[u] > depth[v]:\n",
    "                u, v = v, u\n",
    "            return u, v\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(m):\n",
    "            u1, v1 = get_edge(i)\n",
    "            for j in range(i + 1, m):\n",
    "                u2, v2 = get_edge(j)\n",
    "                if same_tree[v1][v2]:\n",
    "                    if depth[v1] > depth[v2]:\n",
    "                        scores = [vals[v1], vals[v2] ^ vals[v1], vals[0] ^ vals[v2]]\n",
    "                    else:\n",
    "                        scores = [vals[v2], vals[v1] ^ vals[v2], vals[0] ^ vals[v1]]\n",
    "                else:\n",
    "                    scores = [vals[v1], vals[v2], vals[0] ^ vals[v1] ^ vals[v2]]\n",
    "                scores = sorted(scores)\n",
    "                ans = min(ans, scores[-1] - scores[0])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        t = reduce(ixor, nums)\n",
    "        fa = defaultdict(set)\n",
    "        p = [0] * n\n",
    "\n",
    "        def dfs(node, pre):\n",
    "            if node != 0:\n",
    "                fa[node].add(pre)\n",
    "                fa[node] |= fa[pre]\n",
    "            res = nums[node]\n",
    "            for ch in g[node]:\n",
    "                if ch != pre:\n",
    "                    dfs(ch, node)\n",
    "                    res ^= p[ch]\n",
    "            p[node] = res \n",
    "        \n",
    "        dfs(0, -1)\n",
    "        \n",
    "        ans = inf\n",
    "        for i, (a, b) in enumerate(edges):\n",
    "            if b in fa[a]:\n",
    "                a, b = b, a\n",
    "            for j in range(i + 1, len(edges)):\n",
    "                c, d = edges[j]\n",
    "                if d in fa[c]:\n",
    "                    c, d = d, c\n",
    "                \n",
    "\n",
    "                if b in fa[d]:\n",
    "                    x = p[d]\n",
    "                    y = p[b] ^ p[d]\n",
    "                    z = t ^ x ^ y\n",
    "                    ans = min(ans, max(x, y, z) - min(x, y, z))\n",
    "                elif d in fa[b]:\n",
    "                    x = p[b]\n",
    "                    y = p[d] ^ p[b]\n",
    "                    z = t ^ x ^ y\n",
    "                    ans = min(ans, max(x, y, z) - min(x, y, z))\n",
    "                else:\n",
    "                    x = p[b]\n",
    "                    y = p[d]\n",
    "                    z = t ^ x ^ y\n",
    "                    ans = min(ans, max(x, y, z) - min(x, y, z))\n",
    "\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
